public class Test {
    /*回溯算法的两种视角——以数字的视角*/
    //canPartitionKSubsets方法表示：将nums[]中的数字放入k个桶中有几种方法
    boolean canPartitionKSubsets(int[] nums,int k){
        //分组数大于数组长度
        if(k > nums.length){
            return false;
        }
        int sum = 0;
        //得出nums[]中的数字之和
        for(int v : nums){
            sum += v;
        }
        //如果数字之和不能平均到每一个桶中，返回false
        if(sum % k != 0){
            return false;
        }
        int[] bucket = new int[k];//定义桶
        int target = sum / k;//理论上每个桶中数字之和
        return backtrack(nums,0,bucket,target);
    }
    //backtrack方法表示：nums[]从index下标开始
    // 是否能划分成 k 个和为 target 的子集
    boolean backtrack
        (int[] nums, int index, int[] bucket, int target) {
        //结束条件:当index到达数组末尾时，每个桶中的数字之和是否达到预期
        if(index == nums.length){
            for (int i = 0; i < bucket.length; i++) {
                if(bucket[i] != target){
                    return false;
                }
            }
            return true;
        }
        //遍历选择列表，每个小球（数字）可能放入的桶
        //选择列表中是桶
        for (int i = 0; i < bucket.length; i++) {
            //结束条件
            if(bucket[i] + nums[index] > target){
                continue;
            }
            //做选择
            bucket[i] += nums[index];
            //进入下一层决策树，对下一个小球进行判断
            if(backtrack(nums,index+1,bucket,target)){
                return true;
            }
            //撤销选择
            bucket[i] -= nums[index];
        }
        return false;
    }
}
